This invention relates to a system for numerical division and, particularly, to a method and apparatus for non-restoring numerical division. The invention has application in the central processing unit of a high-speed digital computer.
In the course of normal operation, a digital computer performs numerous calculations including addition, subtraction, multiplication, and division. Division is, by far, the most complex of these operations, typically requiring more hardware and computational time than the other operations. The art provides a variety of division techniques, which have in common the utilization of an iterative method for quotient production. The iterative method generally involves generating a single quotient digit in each iterative cycle. Three of the prior art techniques are discussed below.
A restoring division technique is characterized by the selection of quotient digits in the range 0, 1, . . . , (.beta.-1); where .beta. is the radix of the division. Thornton, Design of a Computer--The Control Data 6600, (Scott, Foresman and Co., Glenview, Ill., 1970, pp. 101-105) discloses a radix-4 divider employing this division technique. The apparatus incorporates three adder/subtractor units for the simultaneous calculation of candidate divisor multiples and operates according to a method similar to that of manual, pencil-and-paper division.
A second division technique, non-restoring division, is characterized by the selection of quotient digits having the values -(.beta.-1), . . . , -2, -1, 1, 2, . . . , (.beta.-1). A procedure employing a modified form of this technique is discussed by Nandi et al in "A Simple Technique for Digital Division" (Communications of the ACM, No. 10, 1967, pp. 299-301). In the quotient digit-producing iterative phase, the Nandi et al method generates successive "partial remainders," values reflecting the difference between the numerator and the multiplicative product of the denominator and the previously generated quotient digits. Within the iterative phase, a single radix-.beta. quotient digit is generated as a mathematical function of each partial remainder. In addition to the non-restoring quotient digit values listed above, quotient digits generated according to the Nandi et al method can have the value zero.
A variant of the non-restoring division technique is provided by SRT division, which is also characterized by the selection of quotient digits in the range -(.beta.-1), . . . , -1, 0, 1, . . . , (.beta.-1). A discussion of the SRT technique is provided by Robertson, "A New Class of Digital Division Methods," IRE Transactions on Electronic Computers, vol. EC-7, pp. 218-222, Sept., 1958. The Robertson method employs an iterative process similar to that used by the Nandi et al. However, in Robertson, each quotient digit is generated by operation of a selection circuit, which incorporates a large look-up table.
Drawbacks presented by the prior division methods are numerous. In Thornton, for example, the performance increases do not offset the costs associated with the increased hardware requirements. Both Robertson and Nandi et al generate quotient digits in a manner which requires increased hardware in order to achieve conversion of individual quotient digits to a conventional, restoring form. Nandi et al, further, requires examination, in some cases, of two leading radix-.beta. digits of a partial remainder in order to produce a single quotient digit. Moreover, the Robertson method requires a look-up table having a size which rapidly increases as a function of increased radix. Further, this method requires a large data path length, i.e., the bit-wise length of signals transferred between divider elements.
In light of the deficiences presented by the prior art division methods, an object of this invention is to provide a method and apparatus to perform digital division which is faster and which requires minimal hardware. Another object of the invention is to provide a division method and apparatus which operates in a higher radix and is thus capable of achieving rapid quotient digit generation. A further object is to provide a division system which requires minimal hardware in order to convert individual iteratively-generated quotient digits to conventional form. An object is also to avoid the utilization of an extensive look-up table and the utilization of a large data path length.
Other objects and features of this invention are evident in the illustrations and description below.